A directory service is the central point where network services, security services and applications can inform other entities in the network about their services, thus forming an integrated distributed computing environment. With more and more applications and system services demanding a central information repository, the next generation directory service will need to provide system administrators with a data repository that can significantly ease administrative burdens. In addition, the future directory service must also provide end users with a rich information data warehouse that allows them to access department or company employee data, as well as resource information, such as name and location of printers, copy machines, and other environment resources. In the Internet/intranet environment, it will be required to provide user access to such information in a secure manner.
To this end, the Lightweight Directory Access Protocol (LDAP) has emerged as an Internet Engineering Task Force (IETF) open standard to provide directory services to applications ranging from e-mail systems to distributed system management tools. LDAP is an evolving protocol that is based on a client-server model in which a client makes a TCP/IP connection to an LDAP server, sends requests, and receives responses. The LDAP information model, in particular, is based on an “entry”, which contains information about some object. Entries are typically organized in a specified tree structure, and each entry is composed of attributes.
LDAP provides the capability for directory information to be queried or updated. However, current LDAP implementations support only Boolean queries, which are too limited for many of the current applications. For example, in a DEN (Directory Enabled Network) application, an LDAP query cannot be used to identify the highest priority network management policy in the directory that matches a given profile. To retrieve such information, DEN applications would have to specify not only which directory entries need to be accessed, but also how to access them, using long sequences of LDAP queries—an undesirable alternative.
Many of the new generation of directory applications will require the use of richer query languages that include hierarchical and aggregate selection queries that can be efficiently evaluated (in terms of linear time and I/O complexities) in a centralized directory. For the most part, the newer directories are distributed in nature, where the data is stored on a collector of autonomous directory servers. While such an arrangement allows for conceptual unity, the distributed directory architecture is not well-supported by conventional relational and object-oriented database.
The conceptually unified nature of distributed directories encourages the use of queries without having to be aware of the location of individual directory entries. It is the task of the directory servers and the directory client (which mediates between the user and the servers) to evaluate these queries in a distributed fashion. Distributed evaluation of LDAP (i.e., Boolean) queries is currently performed using the “referral” mechanism, where a server can return references to a client identifying other servers that may contain answers to the query. Thus, distributed query answering does not involve server-to-server communication, which can consume considerable server resources, especially when simultaneously processing thousands of user queries. There are, however, some disadvantages associated with the referral mechanism. Most importantly, if a directory server becomes unavailable, it can create “islands” of directory servers that are disconnected from each other. Even in the circumstance where all servers are available, distributed query evaluation requires a sequence of client-server interactions, involving multiple servers, which can be quite inefficient, especially when the director server topology has long paths.
Thus, a need remains in the art for an improved scheme for query evaluation in directories in a distributed environment, and which can support complex hierarchical and aggregate queries, as well as the simpler LDAP Boolean queries.